The present invention relates to a method and apparatus for encoding and decoding digital images including transcoding to and from other compression formats. The present invention is not limited to still image technologies and may also be used in video image technologies.
In the current baseline JPEG standard it is necessary to substantially decode all the transform coefficients of an 8xc3x978 block before the next 8xc3x978 block can be decoded. Thus the time required to decode any lower resolution version of the image is bound by the time to decode all the coefficients. This time actually significantly constrains the decoding time, especially for the smallest resolutions.
The JPEG standard also provides for redundant hierarchical encoding. The image is encoded at multiple resolutions so that lower resolution versions may be accessed without first having to decompress the image at its full resolution. However this results in large compression files which contain more information than is desirable.
The JPEG standard also provides for non redundant hierarchical encoding such as spectral selection. However these methods are inefficient in the coding of the image
It is an object of the invention to ameliorate one or more of the above mentioned disadvantages of the prior art.
According to a first aspect of the invention, there is provided an image encoding method comprising the steps of: (a) dividing an image into a plurality of blocks which are composed of (Axc3x97B) pixels, A and B being an integer two or more;(b) converting pixels into coefficients in plural frequency regions in the block basis; (c) combining the coefficients of the same frequency region in different blocks to obtain a group of coefficients; and (d) encoding the group of coefficients by the group.
According to a second aspect of the invention, there is provided a method of representing a digital image to provide a coded representation, said method comprising the steps of: (a) dividing said digital image into a plurality of blocks of pixels; (b) transforming each block of pixels into a block of transform coefficients, where each transform coefficient is represented by a predefined bit sequence; (c) rearranging the transform coefficients into a plurality of groups each having one or more subgroups of transform coefficients, wherein said transform coefficients of the same spatial frequency region are grouped together in the same group; (d) selecting in turn each subgroup as a region and setting a predetermined maximum bit plane as the current bit plane; (e) scanning the significance of each bitplane of said selected region from said current bitplane towards a predetermined minimum bitplane, and providing a first token for each insignificant bitplane and a second token for a significant bitplane in said coded representation until a significant bitplane is determined and setting said determined significant bitplane as the current bitplane; (f) partitioning said selected region into two or more subregions having a predetermined form, and setting each of said subregions as said selected region; and (g) repeating steps (e) and (f) for each selected region in turn, commencing from said current bit plane until the predetermined minimum bitplane has been reached, or said selected region has a predetermined size, and coding said transform coefficients of said selected region and providing said coded transform coefficients in said coded representation.
According to a third aspect of the invention, there is provided a method of encoding an image. The method includes the step of dividing the image into a plurality of blocks of pixels. The method also includes the step of transforming the blocks of pixels into respective blocks of transform coefficients, wherein each block of transform coefficients comprises a plurality of subgroups of transform coefficients. The subgroups of each block are associated with respective spatial frequency regions of the block and are capable of being hierarchically inverse transformed to reproduce a number of resolutions of a sub-image of the image. The method further includes the step of rearranging all the subgroups of transform coefficients from all the blocks into groups of transform coefficients, wherein each group comprises those subgroups associated with the same spatial frequency regions from all the blocks of transform coefficients. The method further includes the step of encoding the groups in turn beginning with a first group and continuing in sequence through to a last group, wherein each group is encoded such that a decoder is capable of decoding each group substantially independently of any other group.
According to a fourth aspect of the invention, there is provided a method for decoding a coded representation of a digital image, the coded representation comprising in turn a plurality of encoded groups of transform coefficients, commencing with a first group and continuing in sequence through to a last group. Each encoded group comprises subgroups of transform coefficients associated with the same spatial frequency regions from respective blocks of transform coefficients. The method includes the step of selecting a resolution mode. The method also includes the step of decoding the encoded groups in turn beginning with the first encoded group and continuing in sequence until a number of encoded groups have been decoded, wherein the number is an integer and is determined in response to the resolution mode. The method further includes the step of rearranging all of the transform coefficients of the decoded groups into a plurality of mxc3x97m complete blocks of the transform coefficients, where m is an integer and is dependent on the selected resolution mode. The method further includes the step of inverse transforming each of the mxc3x97m blocks of transform coefficients, if necessary, to derive a block of pixels. Also included is the step of combining the blocks of pixels to reconstitute the image at the selected resolution.
According to a fifth aspect of the invention, there is provided a method for decoding a coded representation of a digital image, said image comprises a plurality of blocks of pixels having associated therewith blocks of transform coefficients which have been rearranged into a plurality of groups each comprising one or more subgroups of transform coefficients, said method comprising the steps of: (a) selecting a resolution mode; (b) decoding the groups in turn beginning with a first group and continuing in sequence until a number of groups have been decoded, wherein said number is determined in response to said resolution mode; and wherein said decoding step comprises the following sub-steps (b)(i) selecting in turn each said subgroup of the groups to be decoded as a region; (b)(ii) scanning said coded representation associated with said selected region, said coded representation comprising a first token for each insignificant bitplane of said coefficients, a second token for each significant bitplane of said coefficients, and zero or more coded coefficients; (b)(iii) if a first token is determined, providing an insignificant bitplane in an output stream for a current bitplane of coefficients of said selected region; (b)(iv) if a second token is determined, providing a significant bitplane in said output stream for said current bitplane of said coefficients of said selected region and partitioning said selected region into two or more subregions having a predetermined form, and setting each of said subregions as said selected region; and (b)(v) repeating steps (b)(ii) to (b)(iv) commencing from a predetermined bitplane until a predetermined minimum bit plane has been reached, or until said selected region has a predetermined size wherein a coded transform coefficient of said selected region is decoded; and (b)(vi) providing said selected subgroups of decoded transform coefficients as an output; (c) rearranging all of the decoded transform coefficients of said selected subgroups into a plurality of nxc3x97n blocks of said transform coefficients, where n is an integer and is dependent on the selected resolution mode; (d) inverse transforming each of said nxc3x97n block of transform coefficients, if necessary, to derive a nxc3x97n block of pixels; and (e) combining said blocks of pixels to reconstitute the digital image or a resolution thereof.
According to a sixth aspect of the invention, there is provided a method of transcoding a JPEG encoded digital image to provide a coded representation in another format. The method includes the step of entropy decoding the JPEG digital image to generate blocks of transform coefficients, wherein each block of transform coefficients comprises a plurality of subgroups of transform coefficients, wherein the subgroups of each block are associated with respective spatial frequency regions of the block and are capable of being hierarchically inverse transformed to reproduce a number of resolutions of a sub-image of the image. The method also includes the step of rearranging all the subgroups of transform coefficients from all the blocks into groups of transform coefficients, wherein each group comprises those subgroups associated with the same spatial frequency regions from all the blocks of transform coefficients. The method further includes the step of encoding the groups in turn beginning with a first group and continuing in sequence through to a last group, wherein each group is encoded such that a decoder is capable of decoding each group substantially independently of any other group.
According to a seventh aspect of the invention, there is provided a method of transcoding a coded representation of a digital image to a JPEG encoded image, the coded representation comprising in turn a plurality of encoded groups of transform coefficients, commencing with a first group and continuing in sequence through to a last group. Each encoded group comprises subgroups of transform coefficients associated with the same spatial frequency regions from respective blocks of transform coefficients. The method includes the step of selecting a resolution mode. The method also includes the step of decoding the encoded groups in turn beginning with a first encoded group and continuing in sequence until a number of encoded groups have been decoded, wherein the number is an integer and is determined in response to the resolution mode. The method further includes the step of rearranging all of the transform coefficients of the decoded groups into a plurality of mxc3x97m complete blocks of the transform coefficients, where m is an integer and is dependent on the selected resolution mode. The method further includes the step of entropy encoding the mxc3x97m blocks of transform coefficients to form a JPEG digital image.
According to an eighth aspect of the invention, there is provided an image coding method comprising the steps of dividing an image into a plurality of blocks of pixels; transforming said blocks of pixels into respective blocks of transform coefficients in accordance with a two dimensional DCT transform, wherein each block of transform coefficients is an 8xc3x978 block of coefficients having a DC transform coefficient and 63 AC transform coefficients; rearranging the transform coefficients into a plurality of groups, wherein a first said group comprises the DC coefficients, a second said group comprises AC01 AC10 and AC11 transform coefficients, a third said group comprises AC02, AC03, AC12, AC13, AC20, AC21, AC30, AC31, AC22, AC23, AC32, AC33 transform coefficients, a fourth said group comprises AC04, AC05, AC06, AC07, AC14, AC15, AC16, AC17, AC24, AC25, AC26, AC27, AC34, AC35, AC36, AC37, AC40, AC50, AC60, AC70, AC41, AC51, AC61, AC71, AC42, AC52, A62, AC72, AC43, AC53, AC63, AC73, AC44, AC45, AC46, AC47, AC54, AC55, AC56, AC57, AC64, AC65, A66, AC67, AC74, AC75, AC76, and AC77 transform coefficients, where ACij is the AC component at the ith row jth column of the block; encoding the groups of coefficients by group, wherein each group is encoded such that a decoder is capable of decoding each group substantially independently of any other group.
According to other aspects of the invention, there is provided apparatus for implementing any one of the aforementioned methods.
According to other aspects of the invention there is provided computer program products comprising a computer readable medium having recorded thereon a computer program for implementing any one of the methods described above.